package Demo05;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        /*String s = "12";
        System.out.println(solution.numDecodings3(s));*/
        System.out.println(solution.nthUglyNumber(10));
    }
}


class Solution {

    public int nthUglyNumber(int n) {
        int[] dp = new int[n+1];
        int i = 1;
        dp[1] = 1;
        int i2 = 1;
        int i3 = 1;
        int i5 = 1;
        while (i<n) {
            int a = dp[i2] * 2;
            int b = dp[i3] * 3;
            int c = dp[i5] * 5;

            int min = Math.min(Math.min(a,b), c);
            if(min==a) {
                i2++;
            }
            if(min==b) {
                i3++;
            }
            if(min==c) {
                i5++;
            }
            i++;
            dp[i] = min;
        }
        return dp[n];
    }

    public int numDecodings3(String s) {

        int[] dp = new int[s.length()+1];
        dp[s.length()] = 1;
        for (int i = s.length() - 1; i >= 0; i--) {
            if(s.charAt(i)=='0') {
                dp[i] = 0;
                continue;
            }
            dp[i] = dp[i+1];
            if((i+1<=s.length()-1)&&((s.charAt(i)-'0')*10+s.charAt(i+1)-'0'<=26)) {
                dp[i] += dp[i+2];
            }
        }
        return dp[0];
    }

    private int numDecodingsPart3(int index, String s, int[] dp) {
        if(index >= s.length()) {
            return 1;
        }
        if(s.charAt(index)=='0') {
            return 0;
        }
        if(dp[index]!=-1) {
            return dp[index];
        }
        int fre = numDecodingsPart1(index+1, s);
        if((index+1<=s.length()-1)&&((s.charAt(index)-'0')*10+s.charAt(index+1)-'0'<=26)) {
            fre += numDecodingsPart1(index+2, s);
        }
        dp[index] = fre;
        return fre;
    }
    public int numDecodings2(String s) {

        int[] dp = new int[s.length()];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }
        return numDecodingsPart2(0, s, dp);
    }

    private int numDecodingsPart2(int index, String s, int[] dp) {
        if(index >= s.length()) {
            return 1;
        }
        if(s.charAt(index)=='0') {
            return 0;
        }
        if(dp[index]!=-1) {
            return dp[index];
        }
        int fre = numDecodingsPart1(index+1, s);
        if((index+1<=s.length()-1)&&((s.charAt(index)-'0')*10+s.charAt(index+1)-'0'<=26)) {
            fre += numDecodingsPart1(index+2, s);
        }
        dp[index] = fre;
        return fre;
    }

    public int numDecodings1(String s) {
        return numDecodingsPart1(0, s);
    }
    private int numDecodingsPart1(int index, String s) {
        if(index >= s.length()) {
            return 1;
        }
        if(s.charAt(index)=='0') {
            return 0;
        }
        int fre = numDecodingsPart1(index+1, s);
        if((index+1<=s.length()-1)&&((s.charAt(index)-'0')*10+s.charAt(index+1)-'0'<=26)) {
            fre += numDecodingsPart1(index+2, s);
        }
        return fre;
    }


}

